|
In computer science, tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting (examining and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a binary tree, but they may be generalized to other trees as well. == Types== Compared to linear data structures like linked lists and one-dimensional arrays, which have a canonical method of traversal (namely in linear order), tree structures can be traversed in many different ways. Starting at the root of a binary tree, there are three main steps that can be performed and the order in which they are performed defines the traversal type. These steps (in no particular order) are: performing an action on the current node (referred to as "visiting" the node), traversing to the left child node, and traversing to the right child node. Traversing a tree involves iterating over all nodes in some manner. Because from a given node there is more than one possible next node (it is not a linear data structure), then, assuming sequential computation (not parallel), some nodes must be deferred – stored in some way for later visiting. This is often done via a stack (LIFO) or queue (FIFO). As a tree is a self-referential (recursively defined) data structure, traversal can be defined by recursion or, more subtly, corecursion, in a very natural and clear fashion; in these cases the deferred nodes are stored implicitly in the call stack. The name given to a particular style of traversal comes from the order in which nodes are visited. Most simply, does one go down first (depth-first: first child, then grandchild before second child) or across first (breadth-first: first child, then second child before grandchildren)? Depth-first traversal is further classified by position of the root element with regard to the left and right nodes. Imagine that the left and right nodes are constant in space, then the root node could be placed to the left of the left node (pre-order), between the left and right node (in-order), or to the right of the right node (post-order). There is no equivalent variation in breadth-first traversal – given an ordering of children, "breadth-first" is unambiguous. For the purpose of illustration, it is assumed that left nodes always have priority over right nodes. This ordering can be reversed as long as the same ordering is assumed for all traversal methods. Depth-first traversal is easily implemented via a stack, including recursively (via the call stack), while breadth-first traversal is easily implemented via a queue, including corecursively. Beyond these basic traversals, various more complex or hybrid schemes are possible, such as depth-limited searches like iterative deepening depth-first search. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tree traversal」の詳細全文を読む スポンサード リンク
|